package com.dycong.common.leetcode;

import java.util.PriorityQueue;

/**
 * @author dycong
 * @date 2019/11/18 15:21
 */
public class FindKthLargest_215 {

    public static void main(String[] args) {
        FindKthLargest_215 findKthLargest_215 = new FindKthLargest_215();
        int[] nums = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        System.out.println(findKthLargest_215.findKthLargest(nums, 4));
        System.out.println(findKthLargest_215.findKthLargest_heap(nums, 4));
    }

    /**
     * 堆
     * 思路是创建一个大顶堆，将所有数组中的元素加入堆中，并保持堆的大小小于等于 k。这样，堆中就保留了前 k 个最大的元素。这样，堆顶的元素就是正确答案。
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        // init heap 'the smallest element first'
        //todo java.util.PriorityQueue 是一个小顶堆
        PriorityQueue<Integer> heap =
                new PriorityQueue<Integer>((n1, n2) -> n1 - n2);

        // keep k largest elements in the heap
        for (int n : nums) {
            heap.add(n);
            if (heap.size() > k)
                heap.poll();
        }

        // output
        return heap.poll();

    }

    /**
     * k 大 小顶堆
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_heap(int[] nums, int k) {
        // 建一个大小为k+1(第一个结点不使用)的数组
        int[] heap = new int[k + 1];
        for (int i = 0; i < k; i++) {
            heap[i + 1] = nums[i];
        }
        // 堆化。建立一个大小为k的小顶堆
        // 从最后一个非叶子结点自下往上开始进行堆化，该结点堆化完后就轮到前一个非叶子结点再自上往下进行堆化
        for (int i = k / 2; i > 0; i--) {
            min_heapify(heap, k + 1, i);
        }

        // 继续遍历数组中剩余的数字，并与堆顶元素进行比较，
        // 若大于堆顶元素，则替换掉堆顶元素，并自顶向下堆化
        for (int i = k; i < nums.length; i++) {
            if (nums[i] > heap[1]) {
                heap[1] = nums[i];
                min_heapify(heap, k + 1, 1);
            }
        }
        return heap[1];
    }

    /**
     * 自顶向下堆化。一般在删除堆顶结点后，把最后一个结点放到堆顶的时候使用。
     * 即这时堆中已经是部分堆化
     *
     * @param heap
     * @param len
     * @param index
     */
    private void min_heapify(int[] heap, int len, int index) {
        while (true) {
            // 找出当前结点和两个直接子结点的最小值
            int minPos = index;
            if (2 * index < len && heap[2 * index] < heap[minPos]) {
                minPos = 2 * index;
            }
            if (2 * index + 1 < len && heap[2 * index + 1] < heap[minPos]) {
                minPos = 2 * index + 1;
            }
            // 若当前结点是最小的，说明下面的是堆化好的了，直接退出循环
            if (minPos == index) {
                break;
            }
            // 当前结点与最小值进行交换
            swap(heap, index, minPos);
            // 当前结点更改为最小直接子结点，继续往下堆化
            index = minPos;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
